package algorithmTopics.array;


public class test10 {
    public static void main(String[] args) {

        test10 test7 = new test10();
        /*char[][] board = {
                {'8', '3', '.', '.', '7', '.', '.', '.', '.'},
                {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                {'.', '.', '.', '.', '8', '.', '.', '7', '9'}
        };*/
        char[][] board = {
                {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
                {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                {'.', '.', '.', '.', '8', '.', '.', '7', '9'}
        };
        System.out.println(test7.isValidSudoku(board));
    }
    public boolean isValidSudoku(char[][] board){
        //应该读取一次这个数字，然后在，列/行/9宫格里分别判断有无这个数字重复
        int length = board.length;
        int[][] line =  new int[length][length];
        int[][] column =  new int[length][length];
        int[][] cell =  new int[length][length];
        //遍历一次，把这个数字存到对应的空间即可
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                if (board[i][j] == '.') {
                    continue;
                }
                // 先算出ASCII的差值，转化为int,再转为0-8之间的数字下标，为了不越界
                int num = board[i][j] - '0'  - 1;
                //再计算是第几个9×9的矩阵0-8标注矩阵号
                int k = i/3*3 + j/3;
                if (line[i][num] != 0 || column[j][num] != 0 || cell[k][num] != 0) {
                    return false;
                }
                line[i][num] =  column[j][num] =  cell[k][num] = 1;

            }
        }

        return true;
    }
    //执行用时：
    //3 ms, 在所有 Java 提交中击败了20.92%的用户
    //内存消耗：
    //43.5 MB, 在所有 Java 提交中击败了50.96%的用户
    //通过测试用例：全部
//    public boolean isValidSudoku(char[][] board) {
//        //判断行
//        //占位符
//        int place = 0;
//        HashMap<Character, Integer> mapLine = new HashMap<>();
//        for (int i = 0; i < board.length; i++) {
//            //第一行
//            for (int j = 0; j < 9; j++) {
//                if (mapLine.get(board[i][j]) != null) {
//                    return false;
//                }
//                if (board[i][j] != '.') {
//                    mapLine.put(board[i][j], place);
//                }
//
//            }
//            //清空这一行
//            mapLine.clear();
//        }
//        mapLine.clear();
//        //判断列
//        for (int i = 0; i < board.length; i++) {
//            //第一行
//            for (int j = 0; j < 9; j++) {
//                if (mapLine.get(board[j][i]) != null) {
//                    return false;
//                }
//                if (board[j][i] != '.') {
//                    mapLine.put(board[j][i], place);
//                }
//            }
//            //清空这一行
//            mapLine.clear();
//        }
//        mapLine.clear();
//        //判断3*3的小矩阵,一共有9个
//        int window = 3;
//        //从上到下，再从左到右
//        //行跳，每三步，就跳走
//        for (int k = 0; k < board.length; k+=window) {
//            //列从上到下
//            for (int i = 0; i < board.length; i++) {
//                //列
//                for (int j = k; j < board.length; j++) {
//                    //进行判断重复
//                    if (mapLine.get(board[i][j]) != null) {
//                        return false;
//                    }
//                    if (board[i][j] != '.') {
//                        mapLine.put(board[i][j], place);
//                    }
//                    //每次一行读三个
//                    if ((j + 1) % window == 0) {
//                        break;
//                    }
//                }
//                //向下走了三步了
//                if ((i + 1) % window == 0) {
//                    mapLine.clear();
//                }
//
//            }
//        }
//        return true;
//    }

}
